package fun.ticsmyc.math;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.math
 * @date 2020-10-14 10:44
 */
public class 辗转相除法 {

    /**
     * 欧几里得算法
     * 要保证 a > b ， 若不满足，则交换
     * @param a
     * @param b
     * @return
     */
    private static int gcd(int a ,int b){
        if(a<b){
            int temp =a;
            a=b;
            b=temp;
        }
        if(b ==0){
            return a ;
        }
        return gcd(b,a % b);
    }

    /**
     * 扩展欧几里得算法 求解不定方程：
     * 1. 对于不定整数方程ax+by=m，若 m mod Gcd(a, b)=0,则该方程存在整数解，否则不存在整数解
     * 2. 假如说我们找到了这样一组解x0和y0，那么x0 + (b / gcd) * t和y0 - (a / gcd) * t也是方程的解，这里的t可以取任意整数。
     * @return
     */
    /**
     *
     * @param a 第一个参数
     * @param b 第二个参数
     * @param x x的值，前两个组成的数组
     * @param y y的值，前两个组成的数组
     * @return 返回值为 {最大公约数，x的值，y的值}
     */
    public static long[] ex_gcd(long a, long b, long[] x, long[] y){

        long gcd;
        long[] result = new long[3];

        if(b==0){
            result[0] = a;
            result[1] = x[0];
            result[2] = y[0];
            return result;
        }
        long q=a/b;
        long tx1 = x[0]-q*x[1];
        long ty1 = y[0]-q*y[1];
        long[] tx = {x[1],tx1};
        long[] ty = {y[1],ty1};
        return ex_gcd(b,a%b,tx,ty);
    }

    public static long[] ex_gcd(long a, long b){
        long[] x = {1,0};
        long[] y = {0,1};
        return ex_gcd(a,b,x,y);
    }


    public static void main(String[] args) {
        int a =100;
        int b=200;
        System.out.println("最大公约数为：" + gcd(b,a));
        System.out.println("最小公倍数为："+ b/gcd(b,a)*a);
    }
}
